import numpy as np
import pandas as pd
import seaborn as sns
import matplotlib.pyplot as plt
# k近邻
def knn(k):
    # k:选择样本数
    dis = []
    # 获取每个样本和预测样本点的距离
    # 欧几里得距离dis=√(x-x0)^2+(y-y0)^2
    for i in data:
        d = np.sqrt((x[0]-i[0])**2 + (x[1]-i[1])**2)
        dis.append([d, i[2]])
    dis.sort(key=lambda x: x[0])
    count = {}  # 储存分类几率
    for i in dis[:k]:
        if count.get(i[1]) == None:
            count[i[1]] = 1/i[0]    # 使用距离的倒数作为权重进行处理
        else:
            count[i[1]] += 1/i[0]
    max_key = max(count, key=count.get)
    return {'k值': k, '预测类别': bool(max_key),'不同分类几率': count}

data = np.array([
    [2, 4, 0],
    [4, 2, 0],
    [4, 4, 1],
    [4, 6, 0],
    [6, 2, 1],
    [6, 4, 0]
])
dd1 = pd.DataFrame([
    {'x':2, 'y':4},
    {'x':4, 'y':2},
    {'x':4, 'y':4},
    {'x':4, 'y':6},
    {'x':6, 'y':2},
    {'x':6, 'y':4}])
# 从相关性可看出，该数据集的相关性不强，无法用knn做出有效预测
sns.heatmap(dd1.corr(), annot=True, cmap='YlGnBu')
plt.show()
x = [8, 1]  # 测试样本
print(knn(1))
print(knn(3))
print(knn(5))

import pandas as pd
from math import log
# ID3决策树
df = pd.DataFrame([
    {'Outlook': 'Sunny', 'Temperature': 'Hot', 'Humidity': 'High', 'Wind': 'Low', 'Play': 'No'},
    {'Outlook': 'Sunny', 'Temperature': 'Hot', 'Humidity': 'High', 'Wind': 'High', 'Play': 'No'},
    {'Outlook': 'Overcast', 'Temperature': 'Hot', 'Humidity': 'High', 'Wind': 'Low', 'Play': 'Yes'},
    {'Outlook': 'Rain', 'Temperature': 'Mild', 'Humidity': 'High', 'Wind': 'Low', 'Play': 'Yes'},
    {'Outlook': 'Rain', 'Temperature': 'Cold', 'Humidity': 'Normal', 'Wind': 'Low', 'Play': 'Yes'},
    {'Outlook': 'Rain', 'Temperature': 'Cold', 'Humidity': 'Normal', 'Wind': 'High', 'Play': 'No'},
    {'Outlook': 'Overcast', 'Temperature': 'Cold', 'Humidity': 'Normal', 'Wind': 'High', 'Play': 'Yes'},
    {'Outlook': 'Sunny', 'Temperature': 'Mild', 'Humidity': 'High', 'Wind': 'Low', 'Play': 'No'},
    {'Outlook': 'Sunny', 'Temperature': 'Cold', 'Humidity': 'Normal', 'Wind': 'Low', 'Play': 'Yes'},
    {'Outlook': 'Rain', 'Temperature': 'Mild', 'Humidity': 'Normal', 'Wind': 'Low', 'Play': 'Yes'},
    {'Outlook': 'Sunny', 'Temperature': 'Mild', 'Humidity': 'Normal', 'Wind': 'High', 'Play': 'Yes'},
    {'Outlook': 'Overcast', 'Temperature': 'Mild', 'Humidity': 'High', 'Wind': 'High', 'Play': 'Yes'},
    {'Outlook': 'Overcast', 'Temperature': 'Hot', 'Humidity': 'Normal', 'Wind': 'Low', 'Play': 'Yes'},
    {'Outlook': 'Rain', 'Temperature': 'Mild', 'Humidity': 'High', 'Wind': 'High', 'Play': 'No'},
])
def log_safe(x):
    return log(x,2) if x!=0 else 0
# 计算香农熵
def entroy(p_ls):
    ent = 0
    for p in p_ls:
        ent += -p*log_safe(p)
    return ent

# 计算标签的香农熵
def root_ent(num_T, num_F):
    p_T = num_T/(num_T+num_F)  # 正例占比
    p_F = num_F/(num_T+num_F)   # 反例占比
    return entroy([p_T, p_F])
# 计算各候选标签的香农熵
def info(label, attribute):
    for i in attribute:
        df1 = df[df[label] == i]
        num_T = df1[df1['Wind'] == 'High']['Wind'].count()
        num_F = df1[df1['Wind'] == 'Low']['Wind'].count()
        print(label, num_T, num_F, root_ent(num_T, num_F))
        yield (num_T+num_F)/m*root_ent(num_T, num_F)

df = df.sort_values(by='Wind')
m = len(df.index)   # 整个数据集样本量
# 计算各节点香农熵
# 以Wind为类标签
label_ls = ['Wind', 'Outlook', 'Temperature', 'Humidity', 'Play',]
ent = root_ent(df[df[label_ls[0]] == 'High'][label_ls[0]].count(), df[df[label_ls[0]] == 'Low'][label_ls[0]].count())

# 计算用各标签划分的信息增益
ent1 = sum(info('Outlook',['Sunny', 'Overcast', 'Rain']))
ent2 = sum(info('Temperature',['Hot', 'Mild', 'Cold']))
ent3 = sum(info('Humidity',['High', 'Normal']))
ent4 = sum(info('Play',['Yes', 'No']))
gain1 = ent - ent1
gain2 = ent - ent2
gain3 = ent - ent3
gain4 = ent - ent4
print('Wind香农熵=%.3f' % ent)
print('Wind,Outlook香农熵=%.3f' % ent1)
print('Wind,Temperature香农熵=%.3f' % ent2)
print('Wind,Humidity香农熵=%.3f' % ent3)
print('Wind,Play香农熵=%.3f' % ent4)
print('Wind,Outlook信息增益=%.3f' % gain1)
print('Wind,Temperature信息增益=%.3f' % gain2)
print('Wind,Humidity信息增益=%.3f' % gain3)
print('Wind,Play信息增益=%.3f' % gain4)
